package com.demo.java.alg;

/**
 * 给定一个随机函数f，等概率返回1~5中的一个数字，
 * 这是唯一可以是使用的随机机制，如何实现等概率
 * 返回1~7中的一个数字。
 *
 * 二分等概率生成3两边的数构造二进制，等概率生成0-6范围内的数，加1即为1-7范围内的数
 */
public class ProbabilityRangeNumber {

    public static int f() {
        return (int)(Math.random() * 5 + 1);
    }

    public static int a() {
        int ans = 0;
        do {
            ans = f();
        } while(ans == 3);
        return ans < 3 ? 0 : 1;
    }

    public static int b() {
        int ans = 0;
        do {
            ans = (a() << 2) + (a() << 1) + a();
        } while (ans == 7);
        return ans + 1;
    }

    public static void main(String[] args) {
        int[] arr = new int[7];
        int testNum = 1000000;
        for (int i = 0; i < testNum; i++) {
            arr[b() - 1]++;
        }
        for (int i = 1; i <= arr.length; i++) {
            System.out.println(i + " : " + arr[i - 1]);
        }

        //System.out.println(f());
    }
}
